from tools_algorithm import *


class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        m, n = len(image), len(image[0])
        f = [[[] for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i < m - 2 and j < n - 2:
                    flag = True
                    sm = image[i][j]
                    for p in range(1, 3):
                        if abs(image[i + p][j] - image[i + p - 1][j]) > threshold:
                            flag = False
                        sm += image[i + p][j]
                        if abs(image[i][j + p] - image[i][j + p - 1]) > threshold:
                            flag = False
                        sm += image[i][j + p]

                    for p in range(1, 3):
                        for q in range(1, 3):
                            sm += image[i + p][j + q]
                            if (
                                abs(image[i + p][j + q] - image[i + p - 1][j + q])
                                > threshold
                            ):
                                flag = False
                            if (
                                abs(image[i + p][j + q] - image[i + p][j + q - 1])
                                > threshold
                            ):
                                flag = False
                    if flag:
                        avg = sm // 9
                        for p in range(3):
                            for q in range(3):
                                f[i + p][j + q].append(avg)
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                ans[i][j] = (
                    image[i][j] if len(f[i][j]) == 0 else sum(f[i][j]) // len(f[i][j])
                )
        return ans


s = Solution()
print(
    s.resultGrid(
        image=[[10, 20, 30], [15, 25, 35], [20, 30, 40], [25, 35, 45]], threshold=12
    )
)
